class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return FourSum(num, target);
    }

	vector<vector<int> > FourSum(vector<int> &num, int target) {
		sort(num.begin(), num.end());
		vector<int> record(4);
		vector<vector<int> > result;

		for (int i = 0; i < num.size();) {
			for (int j = i + 1; j < num.size();) {
				int l = num.size() - 1;
				for (int k = j + 1; k < num.size();) {
					while (k < l && num[i] + num[j] + num[k] + num[l] > target) {
						--l;
					}
					if (k == l) {
						break;
					}
					if (num[i] + num[j] + num[k] + num[l] == target) {
						record[0] = num[i];
						record[1] = num[j];
						record[2] = num[k];
						record[3] = num[l];
						result.push_back(record);
					}
					++k;
					while (k < num.size() && num[k - 1] == num[k]) {
						++k;
					}
				}
				++j;
				while (j < num.size() && num[j - 1] == num[j]) {
					++j;
				}
			}
			++i;
			while (i < num.size() && num[i - 1] == num[i]) {
				++i;
			}
		}
		return result;
	}
};